//邻接表

#pragma once

//存储结构
template <typename V,typename E,int M = 10>
struct ALGraph
{
    //弧节点
    struct ArcNode
    {
        E weight;
        int adjvex;
        ArcNode *nextarc;
    };

    //顶点节点
    struct VexNode
    {
        V data;
        ArcNode *firstarc;
    };
    
    //图结构
    VexNode vexs[M];
    int vexnum,arcnum;
    bool visited[M];
};

//初始化图
template <typename V,typename E,int M>
void InitGraph(ALGraph<V,E,M> &G)
{
    G.vexnum = G.arcnum = 0;
}

//销毁图
template <typename V,typename E,int M>
void DestroyGraph(ALGraph<V,E,M> &G)
{
    //释放每个顶点相连的弧节点
    for (int i = 0; i < G.vexnum; i++)
    {
        //释放顶点i相连的弧节点
        auto &h = G.vexs[i].firstarc;
        while (h)
        {
            auto p = h;
            h = p->nextarc;
            delete p;
        }
        
    }
    
    //将顶点数和弧数清零
    G.vexnum = G.arcnum = 0;
}
//添加顶点AddVertex
//向图G中添加顶点vex，返回顶点的编号
template <typename V,typename E,int M>
int AddVertex(ALGraph<V,E,M> &G,V vex)
{
    if(G.vexnum == M) throw "Too many vertexes";

    int v = G.vexnum;
    G.vexs[v].data = vex;
    G.vexs[v].firstarc = nullptr;
    G.vexnum++;

    return v;
}
//添加边AddArc
//向图G中添加S到t的弧，弧的权值为e
template <typename V,typename E,int M>
void AddArc(ALGraph<V,E,M> &G,int s, int t,E e)
{
    if(s<0 || s>= G.vexnum) throw "Invalid vertex s";
    if(t<0 ||t>=G.vexnum) throw "Invalid vertex t";

    using ArcNode = typename ALGraph<V,E,M>::ArcNode;
    //在顶点s的邻接点链表中插入一个弧节点
    auto p = new ArcNode;
    p->weight = e;
    p->adjvex = t;

    p->nextarc = G.vexs[s].firstarc;
    G.vexs[s].firstarc = p;

    G.arcnum++;
}

//从一个顶点出发深度优先搜索DFS
template <typename V,typename E,int M,typename F>
void DFS(ALGraph<V,E,M> &G,int v,F visit)
{
    //访问顶点v
    visit(G.vexs[v].data);
    G.visited[v] = true;
    //依次从v的未访问的邻接点w出发深度优先遍历
    for(auto p=G.vexs[v].firstarc;p;p = p->nextarc){
        int w = p->adjvex;
        if(!G.visited[w])
        DFS(G,w,visit);
    }

}

//深度优先搜索 DFSTraverse
template <typename V,typename E,int M,typename F>
void DFSTraverse(ALGraph<V,E,M> &G,F visit)
{
    //每个顶点的访问标志设成未访问
    for (int v = 0; v < G.vexnum; v++)
    {
        G.visited[v] = false;
    }
    //从一个未访问的顶点出发深度优先搜索
    for (int v = 0; v < G.vexnum; v++)
    {
        if(!G.visited[v]){
            DFS(G,v,visit);
        }

    }
    
}

#include "sqqueue.h"

//从顶点v出发广度优先搜索BFS
template <typename V,typename E,int M,typename F>
void BFS(ALGraph<V,E,M> &G,int v,F visit)
{
    //访问顶点v
    visit(G.vexs[v].data);
    G.visited[v] = true;
    //利用队列实现广度优先搜索
    SqQueue<int , M*M> Q;
    InitQueue(Q);
    EnQueue(Q,v);
    while (!QueueEmpty(Q))
    {
        //取出访问过的顶点v
        int v;
        DeQueue(Q,v);
        //依次访问v的未访问的邻接点W并且入队列
        for (auto p=G.vexs[v].firstarc;p;p = p->nextarc)
        {
            int w = p->adjvex;
            if (!G.visited[w])
            {
                visit(G.vexs[w].data);
                G.visited[w]=true;
                //入队列
                EnQueue(Q,w);
            }
            
        }
        
    }
    
}

//广度优先搜索BFSTraverse
template <typename V,typename E,int M,typename F>
void BFSTraverse(ALGraph<V,E,M> &G,F visit)
{
    //初始化顶点的访问标志visited为未访问
    for (int v = 0; v < G.vexnum; v++)
    {
        G.visited[v] = false;
    }
    
    //从一个未访问的顶点v出发广度优先搜索
    for(int v = 0; v<G.vexnum; v++){
        if(!G.visited[v]){
            BFS(G,v,visit);
        }
    }
}